package com.example.leetcode;

/**
 * 动态规划  * 参考题解 * 可以优化时间
 * 矩阵区域和
 */
public class Demo1314 {
    public static void main(String[] args) {
        int[][] ans=new int[1][1];
        ans[0][0]+=1;
        System.out.println(ans[0][0]);
    }

    /**
     * 自定义解法
     * @param mat
     * @param k
     * @return
     */
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int[] ints = mat[0];
        int n = ints.length;
        int m = mat.length;
        int[][] ans=new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int l = i-k; l <=i+k ; l++) {
                    if (l<0 || l>=m){
                        continue;
                    }
                    for (int o = j-k; o <=j+k; o++) {
                        if (o<0 || o>=n){
                            continue;
                        }
                        ans[i][j]+=mat[l][o];
                    }
                }
            }
        }

        return ans;
    }

    public int[][] matrixBlockSum1(int[][] mat, int k) {

        int m = mat.length;
        if (m >0){
            int n=mat[0].length;
            //1.求sum
            int[][]  sums=new int[m+1][n+1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j <n ; j++) {
                    sums[i+1][j+1]=sums[i+1][j]+sums[i][j+1]-sums[i][j]+mat[i][j];
                }
            }
            //2.求ans
            int[][]  ans=new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j <n ; j++) {
                    int row1=Math.max(0,i-k);
                    int col1=Math.max(0,j-k);
                    int row2=Math.min(m-1,i+k);
                    int col2=Math.min(n-1,j+k);
                    ans[i][j]=sums[row2+1][col2+1]-sums[row1][col2+1]-sums[row2+1][col1]+sums[row1][col1];
                }
            }

            return ans;
        }
        return null;
    }
}
